/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

// 链表的回文结构,就是检查链表是否是回文结构
// 算法要求时间复杂度为O(n) , 额外空间复杂度为O(1)
// 乍看之下非常难办,其实搞清楚之后还行
// 空间额外复杂度O(1),其实就是设立确定好的变量,不要在循环里面设立变量,这里需要理解好意思
// 回文结构的检测,最好就是用数组来检测,而且在题目要求已经确定好了链表的大小,直接创建相应的数组就行了

class PalindromeList 
{

public:
    bool chkPalindrome(ListNode* A) 
    {

        int arr [900] = { 0 } ;

        ListNode* pcur = A ;

        int num = 0 ;

        while (pcur) // 将链表上面的所有值录入到数组中
        {

            arr [num] = pcur -> val ;

            num++ ; // 这里注意: 在使用完之后,这里的num会多自加一次,会影响后面的数组回文检测

            pcur = pcur -> next ;
        
        }

        int right = 0 ;

        num-- ; // 这里是解决措施

        while (right < num) 
        {

            if (arr [num--] != arr [right++])
            {

                return false ;

            }

        }

        return true ;

        // write code here

    }

};